package leetcode.l0608;

/**
 * 给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。
 * 如果数组中不存在目标值 target，返回[-1, -1]。
 * 输入：nums = [5,7,7,8,8,10], target = 8
 * 输出：[3,4]
 * @author Retain
 * @date 2021/6/8 15:56
 */
public class Medium_在排序数组中查找元素的第一个和最后一个位置_34 {

    public static void main(String[] args) {
        searchRange(new int[]{1},1);
    }
    /**
     * 首先尝试双指针，类似滑动窗口，常规for循环遍历
     * 执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
     * 内存消耗：41.5 MB, 在所有 Java 提交中击败了78.14%的用户
     * @param nums
     * @param target
     * @return
     */
    public static int[] searchRange(int[] nums, int target) {
        int i;
        int start = -1;
        int end = -1;
        boolean found = false;
        if (nums.length != 0) {
            // 找到start
            for (i = 0; i < nums.length; i++) {
                if (nums[i] == target) {
                    found = true;
                    break;
                }
            }
            // 没有找到
            if (!found) {
                return new int[] {start, end};
            }
            //已经找到
            start = i;
            // 从i处开始找end
            while (nums[i] == target) {
                i++;
                // 超出界限
                if (i >= nums.length) {
                    break;
                }
            }
            end = i-1;
        }
        return new int[] {start, end};
    }
}
